\begin{abstract}

 We study a distributed randomized information propagation mechanism
 in networks we call the {\em coalescing-branching} random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied
 ``standard" random walk, and is useful in modeling and understanding the SIS-type of epidemic processes in networks.  It can also be
 helpful in performing light-weight information dissemination in
 resource-constrained networks.  A cobra walk is parameterized by a
 {\em branching factor} $k$.  The process starts from an arbitrary
 node, which is labeled {\em active} for step $1$.  (For instance,
 this could be a node that has a piece of data, rumor, or a virus.) In
 each step of a cobra walk, each active node chooses $k$ random
 neighbors to become active for the next step (``branching").  A node
 is active for step $t+1$ only if it is chosen by an active node in
 step $t$ (``coalescing"). This results in a stochastic process in the
 underlying network with properties that are quite different from both the
 standard random walk (which is equivalent to the cobra walk with branching
 factor $1$) as well as other gossip-based rumor spreading mechanisms.

 We focus on the {\em cover time}\/ of the cobra walk, which is the
 the number of steps for the walk to reach all the nodes, and derive
 almost-tight bounds for various graph classes.  Our main technical
 result is an $O(\log^2 n)$ high probability bound for the cover time
 of cobra walks on expanders, if either the expansion factor or the
 branching factor is sufficiently large; we also obtain an $O(\log n)$
 high probability bound for the {\em partial cover time}, which is the
 number of steps needed for the walk to reach at least a constant
 fraction of the nodes.  We show that the cobra walk takes $O(n \log
 n)$ steps on any $n$-node tree for $k \ge 2$, and $O(n^{1/d}\log n)$
 steps on a $d$-dimensional grid for $k \ge d$, with high probability.

 \junk{which is a fundamental primitive used in a
 wide variety of network applications ranging from token management
 and load balancing to search, routing, information propagation and
 gossip.}  

\junk{
 and the {\em partial cover time},
 which is   We present techniques for analyzing
 cover time of cobra walks in various graph classes.  We derive
 almost-tight bounds on cover time and partial cover time of cobra
 walks in several important classes of graphs including expander
 graphs, trees, and grids.}
%These graphs  arise in many distributed network applications, especially in the modeling and construction of peer-to-peer, overaly, ad hoc, and sensor  networks. 

%A main result of this paper
%is that the time needed by a cobra walk for partial coverage in an $n$-node
%bounded-degree expander is $O(\log n)$ (even with branching factor 2) and for full coverage is
%$O(\log^2 n)$ with high probability.
% Since the cover time of standard
%random walk is $\Theta(n \log n)$ in an expander, this shows that BRW
%gives an exponential speedup.   



%Our BRW results can also be generalized
%to understand the time taken for an epidemic process in an SIS-type
%model to spread in a network.  
%While the persistence time and epidemic
%density of SIS-type epidemic models are well studied, here we analyze
%the time needed for a SIS-type process to reach partial coverage of a
%graph.  By manipulating the branching factor and the time
%that a node remains infected, the process can also be viewed as a
%generalized rumor spreading model, with applications in both
%epidemiology and information dissemination.
\end{abstract}
